1.Field of the Invention
The present invention relates to the field of computer graphics, specifically to the illumination of large three-dimensional (3D) environments.
2.Description of the Related Art
Illumination has been one of the primary concerns in the field of 3D computer graphics since its inception. In order to realistically render a synthetic scene, one must not only capture the reflective properties of the various materials in the scene, but also characterize the illumination at each visible point in the scene. Ideally, this characterization would model every photon impacting that point in the 3D scene, including each photon's wavelength and direction of travel. To do this rigorously would mean tracing each photon's history, from being emitted by a light source, scattering off and through objects in the scene, until ultimately passing through the lens of the virtual camera. However, modeling the history of each photon in this way is computationally unfeasible at any reasonable rate.
In order to make do with limited computational resources, many approximations have been devised over the years to render scenes with varying degrees of realism. One early approximation was Phong's, which primarily addresses the diffuse and specular properties of materials. More elaborate models were created by Blinn, Cook and Torrance and Kajiya. Ray tracing, introduced by Whitted in its more general form (originally presented by Appel as its simplified ray-casting variant), enabled rendering systems to address global illumination effects, such as inter-reflections and cast shadows. Many ray-tracing algorithms have been devised to trace the paths of photons in the scene, employing carefully crafted random distributions to attempt to capture the relevant photons, and can simulate the many “bounces” that a photon may undergo on its semi-random path from light source to camera. Some ray-tracing illumination engines can even simulate subtle effects such as diffraction and subsurface scattering to achieve the pinnacle of realism.
For outdoor scenes, however, the effects of direct illumination and shadowing dominate the visual experience. This is due to the high intensity of the sun or moon's illumination relative to reflected light, and the fact that outdoor scenes tend to be two-and-a-half-dimensional, meaning there are few areas (such as highway overpasses) that are beneath a structure or natural feature. If, therefore, direct illumination and shadows can be computed efficiently, it is possible to render outdoor scenes with realistic illumination at real-time rates (typically 60 Hz or higher). For many applications, however, outdoor scenes cover very large areas (100,000 km2, for example), and the sheer scale of the environment presents unique challenges to efficient illumination.
Direct illumination is a fairly simple problem that scales linearly with the resolution of the display device, and therefore needs no special consideration for large environments. For visual simulation, Phong's approximation is usually sufficient. For sensor simulation (such as night vision goggles (NVGs) and various Infra-Red sensors), a different algorithm is merited (see Castellar et al, U.S. Pat. No. 6,735,557, incorporated here by reference), but the principles are the same: parallel light rays travel directly from a celestial light source to the terrain or other feature and are absorbed, and/or reflected.
Shadowing, however, is a much more computationally intensive problem, because, for each point in the scene, there are many points along the ray to the light source that may or may not be filled by terrain or other feature (such as a mountain). Every one of these points must be tested to see whether or not it occults the light source for the point whose illumination is in question. Moreover, the complexity of the problem increases as the elevation angle of the sun/moon decreases, because the rays travel greater horizontal distances before rising above the tallest features in the scene.
It should be noted that, in outdoor scenes, the dominant occluder is the terrain itself. Shadows cast by the terrain can cover very large areas of terrain, and also features such as trees and man-made structures. In contrast, features cast shadows on small, localized areas. This dichotomy suggests that a hybrid approach to shadow generation, rather than a single global algorithm may be appropriate.
Shadows enhance the realism of visual simulations, and are critical to accurate simulation of night vision goggles. This is due to the great difference in magnitude between moonlight and starlight, versus the difference between direct sunlight and sun illumination scattered through the atmosphere (the blue sky). Shadows can also enhance infrared simulation, in which latent heat stored by the terrain is the source for most of the long-wave IR photons entering the sensor. Areas of terrain that were in shadow for much of the afternoon will be cooler than those in direct sunlight, even at midnight.
Regardless of the shadow algorithm employed, it is important to distinguish between dynamic and static shadowing systems. In a dynamically shadowed environment, the shadows are computed regardless of the position of the light source (e.g. time of day and year) and the position or orientation of movable objects in the scene. In a statically shadowed environment, shadows are computed ahead of time, for a single (or a small number of) light position, and those shadows will be incorrect for any other time of day or positioning of objects and structures. For some applications (such as an architectural walk-through), static shadows may be adequate. Static shadows have the advantage that much more computational power can be brought to bear, as they are computed in an off-line process as part of environment creation.
A variety of shadowing algorithms have been employed for real-time applications, each with its own strengths and weaknesses. The predominant algorithm is known as shadow mapping, introduced by Williams in 1978. In shadow mapping, the 3D scene is rendered from the camera's perspective, and the depth (Z) buffer is stored in a texture map known as the shadow map. When rendering the scene from the camera, the distance from each rendered point in the scene to the light is computed, and if it is greater than the corresponding value in the shadow map, that point is considered to be in shadow. Shadow mapping is useful in that it allows objects to self-shadowed, meaning one part of an object can cast a shadow on another part of the same object. Over large areas, shadow mapping suffers from the limited precision of depth buffers and the limited size of the texture maps. Certain techniques have been recently presented to enhanced large area rendering, involving use of perspective shadow maps to optimize the texel density of the depth map close to the eyepoint, or combining multiple depth maps to cover regions of a scene. Shadow mapping usually requires careful application of a bias term in order to prevent points in the mesh from shadowing themselves. Setting this term can be very subjective and often cannot be constant over the shadow map area.
Another popular algorithm is known as shadow volumes, introduced by Crow in 1977. In this algorithm, special geometry is constructed by projecting rays from the light source, through the each vertex of the object in question, in order to construct a mesh that contains the volume of space in which the light is occulted by that object. Points inside the volume are in shadow, points outside are lit. Most shadow volume real time implementations make use of the stencil planes in graphics hardware systems to build a mask to keep track of shadowed and lit regions, by drawing the front facing and back facing faces of the volume mesh on different passes, and using stencil operations to count how many of each affect each rendered pixel. If the number of front and back facing passes matches, the pixel is lit, if they differ, it is in shadow.
An emerging class of algorithm involves defining a parametric equation such as a spherical harmonic at points in the environment as a preprocessing step, which essentially characterizes what portion of the sky can be seen from each point. Pre-computed Radiance Transfer, presented by Sloan et al in 2002, is the best known example. PRT is an optimization of a technique known as horizon mapping, introduced originally by Max in 1988. This approach produces high-quality illumination at real-time rates, and is applicable to large areas. The preprocessing step is very computationally intense, however, and the parameters can require a great deal of extra storage in the 3D database and corresponding increased bandwidth to transmit them to the graphics engine.
One of the oldest algorithms for shadow computation is light source ray-casting, in which a ray is traversed for each point whose occlusion is in question towards the light source, and objects that may intersect the ray are tested for intersections. A particularly simple form of light source ray casting is ray casting against a height map (a regular grid of height values), since only comparisons of post values against the height of the ray at a given location are needed, avoiding the need for generating and testing actual polygons for ray intersections. While the math required for testing ray intersections is very simple, it has not historically been practical for real-time application over large areas due to the fact that the number of rays and potential intersections both increase geometrically with the size of the environment. Also, efficient shadow-casting requires that the environment database be spatially organized in order to limit intersection tests to objects in the path of the ray. Otherwise, the ratio of relevant to wasted intersection tests rapidly approaches zero.
In the field of terrain rendering there have been many different algorithms that optimize the processing by focusing on specific characteristics of terrain rendering when compared to the general case. One of such methods is the one introduced by Sanz-Pastor and Morgan (U.S. Pat. No. 6,747,649), incorporated here by reference.
It is also common practice to capture the illumination for a given object on a scene on a texture map, separating the actual surface detail of the object from the lighting contribution of the scene in order to achieve per pixel lighting, replacing the per-vertex lighting computations with a modulation map that controls the brightness of the object. Light maps can be pre-computed, or generated dynamically. Either multiple rendering passes or multi-texturing can be used to combine the surface appearance and lighting information from the light map in real time rendering, allowing per-pixel lighting effects with minimal cost, or the lighting contribution can be incorporated into the surface texture and applied as a single map to the object.
Shadowing effects can be also incorporated onto a light map, rendered using any of the previously described algorithms, but applying the shadowed light map to the object geometry can be challenging in many cases. Due to its “2.5D” nature and the distance between the illuminated terrain and the sun or moon illuminating it, terrain is quite amenable to use of per pixel illumination via light maps with a simple planar projection. A detailed description of both shadow casting of height maps and terrain light mapping was presented by Marghidanu in 2002, but both techniques have been used extensively prior to his article. Texture based lighting for sensor rendering on a real time basis was introduced by Castellar et al, including both a per texel computed illumination component as in-band radiance, and a terrain shadow coverage component computed at a higher spatial frequency than the underlying polygon mesh the composite light map is applied to.
An important concept that has been alluded to above is that of computational rates. There are several rate domains in which illumination can be calculated. One such domain is pre-processing, in which shadows are generated prior to real-time simulation, as in static shadows. Another such domain is the per-vertex rate, in which shadows are computed for each vertex in a mesh, and interpolated across each triangle, as in certain parametric algorithms. The highest shadow rate would be to compute the shadows per-pixel, as in shadow mapping with a sufficiently high resolution shadow map that is regenerated every frame (e.g. 1/60th of a second). Both vertex and pixel rate shadow algorithms essentially regenerate all the shadows every frame, which may be unnecessary in many scenes.